The present invention generally relates bitstream generators that use linear feed shift registers.
Bitstream generators are typically used to generate bit stream ciphers. A specific family of bitstream generators is a family of bitstream generators that use linear feed shift registers (LFSRs) to generate stream ciphers. This family of bitstream generators is well known in the art and described, for example, in the following publications:
Applied Cryptography, Protocols Algorithms and Source Code in C, second edition, by Bruce Schneier, John Wiley and Sons Inc., 1996, pages 381-388; and
Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, CRC Press LLC, 1997, pages 202-211.
The disclosures of all references mentioned above and throughout the present specification are hereby incorporated herein by reference.
The present invention seeks to provide an improved bitstream generator that provides better security of a bit stream generated thereby.
In a preferred embodiment of the present invention, a bitstream generator includes a plurality of linear feed shift registers (LFSRs) each of which may be assigned different assignments during different time periods. The output of the bitstream generator is typically used to generate at least one of the following: a bit stream cipher; a hash function; and a pseudo-random binary sequence (PRBS). The bit stream cipher, the hash function and the PRBS may be each used for various application schemes, such as authentication schemes, signature schemes, validation schemes, and verification schemes, and also for various applications, such as integrity check applications, and encryption applications.
The plurality of LFSRs may operate in a xe2x80x9chorseracexe2x80x9d mode of operation by assigning different assignments to at least some of the plurality of the LFSRs during different xe2x80x9cracexe2x80x9d time periods. During a first time period, at least a first one of the plurality of LFSRs is assigned as a generator, and at least a second one of the plurality of LFSRs is assigned as an assignor.
Preferably, all the generators produce LFSR output bits that preferably undergo a selection operation and a combination operation in a first combiner. The first combiner is controlled by a control logic unit and is preferably ultimately operative to generate a single output bit every clock cycle. A collection of such single output bits generated during many time periods forms a stream of bits that may be used as described above.
Preferably, all the assignors produce LFSR output bits that preferably undergo a selection operation, a combination operation, and a scrambling operation in a second combiner. The second combiner is ultimately preferably operative to generate a series of decision bits during the first time period. The series of decision bits is preferably used as an entry to a policy table that preferably determines assignments of each of at least some of the plurality of LFSRs as either a generator or an assignor for a second time period following the first time period. The assignments determined by the policy table are effected by the control logic unit through control of the operation of the plurality of the LFSRs and the second combiner.
It is appreciated that an assignment as an assignor may also include an assignment as a combined assignor and lag generator. The lag generator is preferably operative to determine a lag of N shifts for a specific LFSR during a specific time period, where N is an integer number. Thus, during the specific time period, the specific LFSR performs less bit shifts than an LFSR for which a lag is not determined.
In a preferred embodiment of the present invention at least a third one of the plurality of the LFSRs may be assigned, during the first time period, an assignment as a time-period assignor. All the time-period assignors produce LFSR output bits that undergo a selection operation, a combination operation, and a scrambling operation in a third combiner to ultimately generate a series of time decision bits during the first time period. The series of time decision bits is preferably used as an input to another policy table that determines the second time period, that is, a start time of the second time period, and a duration of the second time period. The start time of the second time period and the duration of the second time period are preferably effected by the control logic unit through control of the operation of the plurality of the LFSRs and the third combiner.
There is thus provided in accordance with a preferred embodiment of the present invention a bitstream generator including a plurality of linear feed shift registers (LFSRs) operative to generate a bit stream and including at least a first LFSR operative, when assigned as a generator during a first time period including at least one clock cycle, to provide an output bit in each clock cycle within the first time period, and at least a second LFSR operative, when assigned as an assignor during the first time period, to provide in each clock cycle an output bit for determining assignments of at least some of the plurality of LFSRs for a second time period following the first time period, the assignments including: assignment as a generator and assignment as an assignor, and a first combiner operative to combine output bits from all of the at least a first LFSR being assigned as generators thereby to produce during each clock cycle a single output bit which is provided to the bit stream.
Preferably, the first combiner includes at least one combinatorial selection logic device which is operative to combine the output bits from all of the at least a first LFSR being assigned as generators to produce a set of intermediate bits, a generator lookup table (LUT) operatively associated with the at least one combinatorial selection logic device and operative to combine the set of intermediate bits to form a single output bit, and an output buffer, operatively associated with the generator LUT and operative to output the single output bit. The combinatorial selection logic device may preferably include a multiplexer (MUX).
Additionally, the bitstream generator may include a second combiner operative to combine output bits from all of the at least a second LFSR that are assigned as assignors to produce a series of decision bits which are applied as an entry to a policy table to determine assignments of each of at least some of the plurality of LFSRs for the second time period. Preferably, the second combiner includes at least one combinatorial selection logic device which is operative to combine the output bits from all of the at least a second LFSR that are assigned as assignors to produce a set of bits every clock cycle, an assignor LUT operatively associated with the at least one combinatorial selection logic device and operative to combine the set of bits to form a single intermediate bit every clock cycle, and a scrambling buffer, operatively associated with the assignor LUT and operative to perform scrambling operations on all intermediate bits generated during the first time period and to output a series of decision bits to the policy table.
Preferably, the assignment as an assignor also includes an assignment as a combined assignor and lag generator. The lag generator is preferably operative to determine, during the first time period, a lag having a length of an integer number N of shifts for an LFSR for the second time period.
Additionally, the bitstream generator also includes at least a third LFSR operative, when assigned as a time-period assignor during the first time period, to provide an output bit for determining a start time and a, length of the second time period.
Further additionally, the bitstream generator also includes a third combiner operative to combine output bits from all of the at least a third LFSR that are assigned as time-period assignors to produce a series of time decision bits, and a policy table operatively associated with the third combiner and operative to accept the series of time decision bits as an entry for determining the start time and the length of the second time period. The bitstream generator may also include a control logic unit operative to control the operation of at least one of the following: the first combiner, the second combiner, the third combiner, and the plurality of LFSRs.
Preferably, the bit stream includes a pseudo random binary sequence. Alternatively, the single output bit outputted by the first combiner includes a result of a hash function.
The plurality of LFSRs may preferably include LFSRs having different lengths. The different lengths are preferably limited to a selected range of lengths.
Preferably, the first time period and the second time period are each only one clock cycle. Alternatively, the first time period and the second time period may be each longer than one clock cycle.
The second time period may follow the first time period after a time delay. The time delay may include at least one clock cycle. Alternatively, the time delay may include a time period having a length of one of the following: the first time period; and the second time period.
There is also provided in accordance with a preferred embodiment of the present invention a method for generating a bit stream, the method including providing a plurality of linear feed shift registers (LFSRs), assigning at least a first LFSR of the plurality of LFSRs during a first time period as a generator which is operative to provide an output bit in each clock cycle within the first time period, assigning at least a second LFSR of the plurality of LFSRs during the first time period as an assignor which is operative, in each clock cycle, to provide an output bit for determining assignments of at least some of the plurality of LFSRs for a second time period following the first time period, the assignments including: assignment as a generator, and assignment as an assignor, and combining output bits from all of the at least a first LFSR of the plurality of LFSRs being assigned as generators to produce during each clock cycle a single output bit which is provided to the bit stream.
Preferably, the combining step includes the steps of combining the output bits from all of the at least a first LFSR of the plurality of LFSRs being assigned as generators to produce a set of intermediate bits every clock cycle, using a generator lookup table (LUT) to combine the set of intermediate bits to form a single output bit, and outputting the single output bit.
Additionally, the method includes the step of combining output bits from all of the at least a second LFSR of the plurality of LFSRs that are assigned as assignors to produce a series of decision bits which are applied as an entry to a is policy table to determine assignments of each of at least some of the plurality of LFSRs for the second time period.
The combining step may preferably include the steps of combining the output bits from all of the at least a second LFSR of the plurality of LFSRs that are assigned as assignors to produce a set of bits every clock cycle, using an assignor LUT to combine the set of bits to form a single intermediate bit every clock cycle, scrambling all single intermediate bits generated during the first time period to generate a series of decision bits, and outputting the series of decision bits to the policy table.
Preferably, the assignment as an assignor also includes an assignment as a combined assignor and lag generator. The lag generator is preferably operative to determine, during the first time period, a lag having a length of an integer number N of shifts for an LFSR for the second time period.
Additionally, the method includes the step of assigning at least a third LFSR of the plurality of LFSRs during the first time period as a time-period assignor which is operative to provide an output bit for determining a start time and a length of the second time period. Further additionally, the method also includes the step of combining output bits from all of the at least a third LFSR of the plurality of LFSRs that are assigned as time-period assignors to produce a series of time decision bits which are applied as an entry to a policy table to determine the start time and the length of the second time period.